/*
 *  Copyright (c) 2004, The University Scheduler Project
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *
 *  - Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *  - Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *  - Neither the name of the University Scheduler Project nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 */

package edu.rpi.scheduler.engine;

import edu.rpi.scheduler.schedb.CourseDescriptor;
import edu.rpi.scheduler.schedb.DefaultSchedule;
import edu.rpi.scheduler.schedb.SectionDescriptor;
import edu.rpi.scheduler.schedb.UniqueSection;
import edu.rpi.scheduler.schedb.WeekMask;
import edu.rpi.scheduler.schedb.spec.Department;
import edu.rpi.scheduler.schedb.spec.Schedule;
import edu.rpi.scheduler.schedb.spec.SchedulerData;
import edu.rpi.scheduler.schedb.spec.SchedulerDataPlugin;
import edu.rpi.scheduler.schedb.spec.Section;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * Represents a set of courses, constraints, and, ultimately, schedules
 * generated by the user. A {@code Scheduler} holds the courses the user
 * wants to take, the sections he or she does not want, the time mask he or she
 * has blocked out, and more. It holds the list of {@code Department}s and
 * {@code Course}s and generates permutations of the selected courses based
 * on the user's constraints to produce {@code Schedule}s. This class also
 * sorts the schedules.
 */
public class SchedulerEngine {
    /**
     * A comparator that sorts {@code UniqueSection} instances in
     * increasing order by their {@code getLowestNumber()} return values.
     */
    private static final Comparator<UniqueSection> LOWNUM_COMPARATOR
            = new Comparator<UniqueSection>() {
        public int compare(UniqueSection o1, UniqueSection o2) {
            return o1.getLowestNumber()
                    .compareTo(o2.getLowestNumber());
        }
    };
    /**
     * A comparator that sorts <code>Map.Entry<?, Set></code> instances in
     * increasing order by how many elements are in the set.
     */
    private static final Comparator<Map.Entry<?,? extends Set<?>>> VALSIZE_COMPARATOR
            = new Comparator<Map.Entry<?,? extends Set<?>>>() {
        public int compare(Map.Entry<?,? extends Set<?>> o1, Map.Entry<?,? extends Set<?>> o2) {
            int s1 = o1.getValue().size();
            int s2 = o2.getValue().size();

            return s1 < s2 ? -1 : (s1 == s2 ? 0 : 1);
        }
    };


    private SchedulerDataPlugin schedulerPlugin = null;
    private SchedulerData schedulerData = null;

    private Map<CourseDescriptor, SelectedCourse> selectedCourses
            = new LinkedHashMap<CourseDescriptor, SelectedCourse>();

    private WeekMask<?> blockedTime = null;
    private Collection<SectionDescriptor> blockedSections
            = new ArrayList<SectionDescriptor>();

    private List<Schedule> possibleSchedules = Collections.emptyList();

    private boolean needsGenerating = true;
    private volatile boolean working;

    private Comparator<? super Schedule> lastComparator = null;

    public SchedulerEngine() {
    }

    public SchedulerEngine(SchedulerData schedulerData) {
        setSchedulerData(schedulerData);
    }

    public synchronized SchedulerData getSchedulerData() {
        return schedulerData;
    }

    public synchronized void setSchedulerData(SchedulerData schedulerData) {
        this.schedulerData = schedulerData;
        schedulerPlugin = schedulerData.getDataContext().getSchedulerPlugin();
        blockedTime = schedulerPlugin.getTimeRepresentation().newWeekMask();
    }

    /**
     * Sets the list of sections within the list of {@linkplain
     * #setSelectedCourses selected courses} that the user does not want to
     * be in. No schedules with these sections will be generated.
     * @param blockedSections the list of sections the user has blocked
     */
    public synchronized void setBlockedSections(Collection<SectionDescriptor> blockedSections) {
        Collection<SectionDescriptor> old = this.blockedSections;

        this.blockedSections = blockedSections;

        if (old.size() != blockedSections.size()
                || (!old.containsAll(blockedSections)
                && !blockedSections.containsAll(old))) {
            setNeedsGenerating();
        }
    }

    /**
     * Sets the time the user has blocked out, disallowing any classes during
     * this time. No schedules will be generated which overlap this time mask.
     * @param mask the time mask the user has blocked out
     */
    public synchronized void setBlockedTime(WeekMask<?> mask) {
        WeekMask<?> old = this.blockedTime;

        WeekMask<?> newBlocked = schedulerPlugin.getTimeRepresentation().newWeekMask();
        newBlocked.merge(mask);
        this.blockedTime = newBlocked;

        if (!newBlocked.equals(old)) {
            setNeedsGenerating();
        }
    }

    /**
     * Returns the time mask that the user has blocked out, disallowing any
     * classes during this time.
     * @return the time mask the user has blocked out
     */
    public synchronized WeekMask<?> getBlockedTime() {
        WeekMask<?> mask = schedulerPlugin.getTimeRepresentation().newWeekMask();
        mask.merge(blockedTime);
        return mask;
    }

    /**
     * Returns the list of sections the user has blocked.
     * @return the list of sections blocked by the user
     */
    public synchronized Collection<SectionDescriptor> getBlockedSections() {
        return blockedSections;
    }

    /**
     * Generates schedules from the given constraints, if necessary. If no
     * constraints have changed since the last call to
     * {@code generateSchedules}, then this call will not do anything.
     */
    public synchronized void generateSchedules() {
        if (working || !needsGenerating) return;
        try {
            working = true;

            List<Schedule> schedules = reallyGenerateSchedules();
            possibleSchedules = new ArrayList<Schedule>(schedules);
            Comparator<? super Schedule> lastcomp = lastComparator;
            if (lastcomp != null) sortBy(lastcomp);
            needsGenerating = false;
        } finally {
            working = false;
        }
        fireGeneratedEvent();
    }

    private Set<EngineListener> listeners = new LinkedHashSet<EngineListener>();

    public synchronized void addEngineListener(EngineListener l) {
        listeners.add(l);
    }

    public synchronized void removeEngineListener(EngineListener l) {
        listeners.remove(l);
    }

    private synchronized void fireGeneratedEvent() {
        for (EngineListener listener : listeners) {
            listener.schedulesGenerated(this);
        }
    }

    private synchronized List<Schedule> reallyGenerateSchedules() {
        List<Schedule> schedules = new ArrayList<Schedule>();

        List<CourseDescriptor> requiredCourses = getRequiredCourses();
        if (!requiredCourses.isEmpty()) {
            List<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> reqsections
                    = getGoodSections(requiredCourses);
            buildRequiredSchedules(schedules, null, reqsections, 0);

            if (schedules.isEmpty()) return schedules;
        }

        List<CourseDescriptor> extraCourses = getExtraCourses();
        List<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> optsections
                = getGoodSections(extraCourses);

        List<Schedule> optschedules = new ArrayList<Schedule>();
        if (!optsections.isEmpty()) {
            if (schedules.isEmpty()) {
                buildExtraSchedules(optschedules, null, optsections, 0);
            } else {
                for (Schedule schedule : schedules) {
                    buildExtraSchedules(optschedules, schedule, optsections, 0);
                }
            }
        }

        List<Schedule> totalSchedules = new ArrayList<Schedule>(schedules.size()
                + optschedules.size());
        totalSchedules.addAll(schedules);
        totalSchedules.addAll(optschedules);

        return totalSchedules;
    }

    public synchronized Collection<SelectedCourse> getSelectedCourses() {
        return new ArrayList<SelectedCourse>(selectedCourses.values());
    }

    public synchronized Collection<CourseDescriptor> getSelectedCourseDescriptors() {
        return new ArrayList<CourseDescriptor>(selectedCourses.keySet());
    }

    public List<CourseDescriptor> getRequiredCourses() {
        return getCoursesByExtraValue(false);
    }

    public List<CourseDescriptor> getExtraCourses() {
        return getCoursesByExtraValue(true);
    }

    private synchronized List<CourseDescriptor> getCoursesByExtraValue(boolean extra) {
        List<CourseDescriptor> list
                = new ArrayList<CourseDescriptor>(selectedCourses.size());
        for (Map.Entry<CourseDescriptor, SelectedCourse> entry
                : selectedCourses.entrySet()) {
            if (entry.getValue().isExtra() == extra) list.add(entry.getKey());
        }
        return list;
    }

    private synchronized
    List<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> getGoodSections(
            List<CourseDescriptor> selected) {
        Map<CourseDescriptor,SortedSet<UniqueSection>> sections
                = new HashMap<CourseDescriptor,SortedSet<UniqueSection>>(selected.size());
        Set<SectionDescriptor> blocked
                = new HashSet<SectionDescriptor>(blockedSections);

        // cache this so we don't keep acessing the field
        WeekMask<?> blockedTime = this.blockedTime;

        for (CourseDescriptor course : selected) {
            Collection<Section> sects = course.getActualCourse().getSections();

            SortedSet<UniqueSection> good
                    = new TreeSet<UniqueSection>(LOWNUM_COMPARATOR);
            Map<WeekMask<?>,UniqueSection> unique
                    = new HashMap<WeekMask<?>, UniqueSection>(sects.size());
            sections.put(course, good);

            Outer: for (Section section : sects) {
                for (SectionDescriptor sd : blocked) {
                    if (sd.getActualSection().equals(section)) continue Outer;
                }

                WeekMask<?> mask = section.getWeekMask();
                UniqueSection sect = unique.get(mask);
                boolean first = sect == null;
                if (first) {
                    sect = new UniqueSection(mask);
                    unique.put(mask, sect);
                }
                sect.addSection(new SectionDescriptor(course, section));

                if (first && sect.getTimeMask().fitsInto(blockedTime)) {
                    good.add(sect);
                }
            }
        }
        Set<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> entrySet = sections.entrySet();


        List<Map.Entry<CourseDescriptor, SortedSet<UniqueSection>>> entries
                = new ArrayList<Map.Entry<CourseDescriptor,
                SortedSet<UniqueSection>>>(entrySet);
        Collections.sort(entries, VALSIZE_COMPARATOR);
        return entries;
    }

    private void buildRequiredSchedules(List<Schedule> schedules, DefaultSchedule schedule,
            List<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> required,
            int index) {
        SchedulerDataPlugin schedulerPlugin = this.schedulerPlugin;

        Set<UniqueSection> reqsections = required.get(index).getValue();
        int newindex = index + 1;
        boolean last = newindex == required.size();

        for (UniqueSection section : reqsections) {
            if (schedule != null && !schedule.canAdd(section)) {
                continue;
            }

            DefaultSchedule sched;
            if (schedule == null) {
                sched = new DefaultSchedule(schedulerPlugin);
            } else {
                sched = new DefaultSchedule(schedulerPlugin, schedule);
            }

            sched.addSection(section);

            if (last) schedules.add(sched);
            else buildRequiredSchedules(schedules, sched, required, newindex);
        }
    }

    private void buildExtraSchedules(List<Schedule>  schedules, Schedule schedule,
            List<Map.Entry<CourseDescriptor,SortedSet<UniqueSection>>> extra,
            int index) {
        SchedulerDataPlugin schedulerPlugin = this.schedulerPlugin;

        Set<UniqueSection> extraSections = extra.get(index).getValue();
        int newindex = index + 1;
        boolean last = newindex == extra.size();

        for (UniqueSection section : extraSections) {
            if (schedule != null && !schedule.canAdd(section)) {
                continue;
            }

            DefaultSchedule sched;
            if (schedule == null) {
                sched = new DefaultSchedule(schedulerPlugin);
            } else {
                sched = new DefaultSchedule(schedulerPlugin, schedule);
            }

            sched.addSection(section);

            schedules.add(sched);

            if (!last) {
                buildExtraSchedules(schedules, sched, extra, newindex);
            }
        }
        if (!last) buildExtraSchedules(schedules, schedule, extra, newindex);
    }

    private synchronized void setNeedsGenerating() {
        needsGenerating = true;
    }

    public synchronized void sortBy(Comparator<? super Schedule> comp) {
        lastComparator = comp;
        Collections.sort(possibleSchedules, comp);
    }

    /**
     * Returns the schedules that have been generated with {@link
     * #generateSchedules}, sorted in the order set by the {@code sortBy*}
     * methods.
     * @return the schedules that have been generated, sorted
     */
    public synchronized List<Schedule> getGeneratedSchedules() { return possibleSchedules; }

    /**
     * Returns the {@code Comparator} being used to sort the schedules.
     * @return the {@code Comparator} being used to sort the schedules
     */
    public synchronized Comparator<? super Schedule> getSortMethod() { return lastComparator; }

    public synchronized boolean isExtra(CourseDescriptor course) {
        SelectedCourse selectedCourse = selectedCourses.get(course);
        return selectedCourse != null && selectedCourse.isExtra();
    }

    public synchronized List<CourseDescriptor> getAllCourses() {
        List<CourseDescriptor> courseList = new ArrayList<CourseDescriptor>(1000);
        Collection<Department> depts = schedulerData.getDepartments();
        for (Department dept : depts) {
            courseList.addAll(CourseDescriptor.getDescriptors(dept,
                    dept.getCourses()));
        }
        return courseList;
    }

    public synchronized void setSelectedCourses(Collection<SelectedCourse> courses) {
        selectedCourses.clear();
        for (SelectedCourse course : courses) addCourse(course);
        setNeedsGenerating();
    }

    public synchronized void addCourse(SelectedCourse course) {
        if (selectedCourses.put(course.getCourse(), course) == null) {
            setNeedsGenerating();
        }
    }

    public synchronized void removeCourse(CourseDescriptor course) {
        if (selectedCourses.remove(course) != null) setNeedsGenerating();
    }

    public synchronized void removeAllCourses() {
        if (!selectedCourses.isEmpty()) {
            selectedCourses.clear();
            setNeedsGenerating();
        }
    }


    public synchronized void removeCourses(Collection<CourseDescriptor> courses) {
        for (CourseDescriptor cd : courses) removeCourse(cd);
    }

    public boolean coursesConflict(CourseDescriptor a, CourseDescriptor b) {
        Collection<Section> sections1 = a.getActualCourse().getSections();
        Collection<Section> sections2 = b.getActualCourse().getSections();
        if (sections1.isEmpty() || sections2.isEmpty()) return false;
        for (Section section : sections1) {
            for (Section section2 : sections2) {
                if (!sectionsConflict(section, section2)) {
                    // we found two sections of these courses that don't conflict!
                    return false;
                }
            }
        }
        return true;
    }

    private boolean sectionsConflict(Section section1, Section section2) {
        return !section1.getWeekMask().fitsInto(section2.getWeekMask());
    }

    public boolean isWorking() {
        return working;
    }

}
